6.3 最短路径算法

在图结构中，最短路径算法 是一类非常重要的算法，它用于找到从一个顶点到另一个顶点的最短路径。

最短路径问题广泛应用于导航、通信网络、路径规划等领域。

最短路径问题 是在图中找到从起点到目标顶点的最短路径，路径长度是由边的权重决定的。对于不同类型的图，最短路径问题可以有多种解法。

最短路径问题的两种主要分类：

  • 单源最短路径：从一个源顶点出发，找到它到其他所有顶点的最短路径。

  • 全源最短路径：找到图中任意两个顶点之间的最短路径。

本节将介绍常见的几种最短路径算法，包括 迪克斯特拉算法（Dijkstra）算法和 贝尔曼-福特（Bellman-Ford）算法，并使用 Go 语言进行实现。

本节代码存放目录为 lesson14

狄克斯特拉算法

Dijkstra 算法 是一种用于解决单源最短路径问题的算法，适用于权重为正的图。

算法步骤如下所示：

  1. 初始化：将起点的距离设为 0，其他顶点的距离设为 ∞（无穷大）。

  2. 对当前顶点的每个未访问的邻接顶点，计算其到起点的距离，更新邻接顶点的最短距离。

  3. 重复步骤 2，直到所有顶点都已访问或找到了目标顶点的最短路径。

算法示例如下所示：

我们以 A 为起点，寻找 A -> D 的最短路径。

图结构：

       (10)
    A ------ B
     \      / \
   (3)\  (1)  (2)
       \ /      \
        C        D
       /        /
      (4)     (6)
        \    /
           E

  1. 初始化：将起点 A 的距离设为 0，其他顶点的距离设为无穷大 ∞。

    这个无穷大表示的是 A 到这个顶点的距离，由于目前还是未知的，所以设置为无穷大。

    随着计算往下进行，这个无穷大会逐渐变小，最终收敛为一个正确的数值。

    表示为：

      A: 0, B: ∞, C: ∞, D: ∞, E: ∞

  2. 第一步：从 A 出发，寻找可以直达的未访问顶点 B 和 C。

    • A -> B 的距离为 10。

    • A -> C 的距离为 3。

    因为 A -> C 的距离较短，因此选择 C 作为当前顶点，并更新最短距离为 3： 

    A: 0, B: 10, C: 3, D: ∞, E: ∞

  3. 第二步：从 C 出发，寻找可以直达的未访问顶点 B 和 E。

    • C -> B 的距离为 1，所以 A -> C -> B 的距离是 3 + 1 = 4（比原来的 A -> B 距离 10 更短）。

    • C -> E 的距离为 4，所以 A -> C -> E 的距离是 3 + 4 = 7。

    更新距离 B 为更短的4，E 为 7： 

    A: 0, B: 4, C: 3, D: ∞, E: 7

  4. 第三步：从 B 出发，寻找可以直达的未访问顶点 D。

    • B -> D 的距离为 2，所以 A -> C -> B -> D 的距离是 4 + 2 = 6。

    更新距离 D 为 6： 

    A: 0, B: 4, C: 3, D: 6, E: 7

  5. 终止：此时，D 的最短路径已经确定，A -> D 的最短路径为 A -> C -> B -> D，总距离为 6。

    虽然 E 也可达，但 A -> E 的距离是 7，大于 A -> D 的 6，因此最短路径为：

    A -> C -> B -> D

从上面我们可以看出，Dijkstra 算法会不断检查从起点到各个顶点的所有可能路径，逐步更新为更短的路径，直到找到最优解。

贝尔曼-福特算法

Bellman-Ford 算法 是另一种用于解决单源最短路径问题的算法，它能够处理带有负权重边的图，并且可以检测负权环。

它的核心思想就是：不断更新从起点到各个顶点的最短距离，直到所有可能的最短路径都被找到。

算法步骤如下所示：

  1. 初始化：设定起点的距离为 0，其他所有顶点的距离设为 ∞（表示未知或非常远）。

  2. 松弛操作：对每条边进行检查，如果通过这条边能找到一条更短的路径，那就更新目标顶点的距离。

  3. 重复松弛：你要经过所有边 V-1 次（V 是顶点数量），确保每个顶点的最短路径都被找到。比如有 5 个顶点，那么就最少要经过 4 次。

  4. 检查负环：再经过一次所有边，如果还能继续更新路径，那就说明有负权环，即无穷循环的负数路径。

算法示例如下所示：

我们以 A 为七点，找到从 A 到每个顶点的最短路径。

图结构：

    A --(1)--> B
     \       /  \
   (4)\    (-2)  (3)
       \  /       \
        C --(1)--> D

  1. 初始化：我们从起点 A 开始，所有点的初始距离如下：

     A: 0, B: ∞, C: ∞, D: ∞

  2. 松弛操作： 我们检查每条边，更新路径。

    • A -> B 距离是 1，现在 B 的最短距离是 1。

      A: 0, B: 1, C: ∞, D: ∞

    • A -> C 距离是 4，现在 C 的最短距离是 4。

      A: 0, B: 1, C: 4, D: ∞

    • B -> C 距离是 -2，如果 A 通过 B 去 C，距离是 1 + (-2) = -1，比 4 小，所以更新 C 的距离为 -1。

      A: 0, B: 1, C: -1, D: ∞

    • B -> D 距离是 3，A 通过 B 到 D，距离是 1 + 3 = 4，更新 D 的距离为 4。

      A: 0, B: 1, C: -1, D: 4

    • C -> D 距离是 1，A 通过 C 到 D 的距离是 -1 + 1 = 0，比 4 小，更新 D 的距离为 0。

      更新后的状态：

      A: 0, B: 1, C: -1, D: 0

  3. 重复松弛：重复步骤 2，共进行 V-1 次（这里是 3 次，因为有 4 个顶点）。经过 3 次松弛后，所有的距离都不会再更新了。

    在我们的这个例子中，后面 2 次松弛的结果都会是与上面相同的，因为已经都是最短的了。

  4. 检查负权环：

    再做一次松弛。如果这时还能更新任何距离，说明存在负权环，否则就没有负环。

那么狄克斯特拉与贝尔曼-福特的主要区别是什么呢？

  • Dijkstra 在对邻接顶点进行计算后，就不会再次计算，一旦更新了某个顶点的最短路径，就不会再重复计算。适用于边较多的图结构。

  • Bellman-Ford 会在每一轮松弛中都对所有边进行检查，哪怕已经得到了最优解，还是会继续执行完多次检查，所以它的执行次数是比 Dijkstra 要多的。适用于带有负权的图结构。

Go 语言的实现

Dijkstra 算法实现

图结构如下所示：

        (10)
    A ------ B
     \      / \
   (3)\  (1)  (2)
       \ /      \
        C        D
       /        /
      (4)     (6)
        \    /
           E

实现代码如下所示：

// Graph 定义图结构，使用邻接表表示
type Graph struct {
    vertices map[string]map[string]int
}

// NewGraph 创建一个新的图
func NewGraph() *Graph {
    return &Graph{
        vertices: make(map[string]map[string]int),
    }
}

// AddVertex 添加顶点到图中
func (g *Graph) AddVertex(vertex string) {
    if g.vertices[vertex] == nil {
        g.vertices[vertex] = make(map[string]int)
    }
}

// AddEdge 添加带权重的有向边
func (g *Graph) AddEdge(v1, v2 string, weight int) {
    g.AddVertex(v1)
    g.AddVertex(v2)
    g.vertices[v1][v2] = weight
}

// Dijkstra 实现 Dijkstra 算法
func (g *Graph) Dijkstra(start string) map[string]int {
    // 初始化距离表，起始点到自己的距离为0，其他点为无穷大
    distances := make(map[string]int)
    for vertex := range g.vertices {
        distances[vertex] = math.MaxInt32
    }
    distances[start] = 0

    // 已访问的顶点
    visited := make(map[string]bool)

    for len(visited) < len(g.vertices) {
        // 从未访问的顶点中选出距离最小的顶点
        var minVertex string
        minDistance := math.MaxInt32
        for vertex, distance := range distances {
            if !visited[vertex] && distance < minDistance {
                minDistance = distance
                minVertex = vertex
            }
        }

        // 标记为已访问
        visited[minVertex] = true

        // 更新邻接顶点的距离
        for neighbor, weight := range g.vertices[minVertex] {
            if newDist := distances[minVertex] + weight; newDist < distances[neighbor] {
                distances[neighbor] = newDist
            }
        }
    }

    return distances
}

func main() {
    // 创建图
    graph := NewGraph()
    graph.AddEdge("A", "B", 10)
    graph.AddEdge("A", "C", 3)
    graph.AddEdge("C", "B", 1)
    graph.AddEdge("C", "D", 8)
    graph.AddEdge("B", "D", 2)
    graph.AddEdge("D", "E", 6)
    graph.AddEdge("C", "E", 4)

    // 确保所有节点都被初始化
    graph.AddVertex("E")

    // 执行 Dijkstra 算法
    distances := graph.Dijkstra("A")

    fmt.Println("最短路径：", distances)
}

执行结果输出如下所示：

最短路径： map[A:0 B:4 C:3 D:6 E:7]

Bellman-Ford 算法实现

图结构如下所示：

    A --(1)--> B
     \       /  \
   (4)\    (-2)  (2)
       \  /       \
        C          D
         \        /
        (3)     (5)
           \    /
             E

实现代码如下所示：

// Graph 定义图结构，使用邻接表表示
type Graph struct {
    vertices map[string]map[string]int
}

// NewGraph 创建一个新的图
func NewGraph() *Graph {
    return &Graph{
        vertices: make(map[string]map[string]int),
    }
}

// AddVertex 添加顶点
func (g *Graph) AddVertex(v string) {
    if g.vertices[v] == nil {
        g.vertices[v] = make(map[string]int)
    }
}

// AddEdge 添加带权重的有向边
func (g *Graph) AddEdge(v1, v2 string, weight int) {
    g.AddVertex(v1)
    g.AddVertex(v2)
    g.vertices[v1][v2] = weight
}

// BellmanFord 实现 Bellman-Ford 算法
func (g *Graph) BellmanFord(start string) (map[string]int, bool) {
    // 初始化距离表，起始点到自己的距离为0，其他点为无穷大
    distances := make(map[string]int)
    for vertex := range g.vertices {
        distances[vertex] = math.MaxInt32
    }
    distances[start] = 0

    // 获取图中所有的边
    edges := g.getAllEdges()

    // 执行 V-1 轮松弛操作
    for i := 0; i < len(g.vertices)-1; i++ {
        for _, edge := range edges {
            if distances[edge.source] != math.MaxInt32 && distances[edge.source]+edge.weight < distances[edge.destination] {
                distances[edge.destination] = distances[edge.source] + edge.weight
            }
        }
    }

    // 检查负权环
    for _, edge := range edges {
        if distances[edge.source] != math.MaxInt32 && distances[edge.source]+edge.weight < distances[edge.destination] {
            return distances, true // 存在负权环
        }
    }

    return distances, false // 没有负权环
}

// Edge 定义边结构
type Edge struct {
    source, destination string
    weight              int
}

// 获取所有的边
func (g *Graph) getAllEdges() []Edge {
    var edges []Edge
    for v1, neighbors := range g.vertices {
        for v2, weight := range neighbors {
            edges = append(edges, Edge{source: v1, destination: v2, weight: weight})
        }
    }
    return edges
}

func main() {
    // 创建图
    graph := NewGraph()
    graph.AddEdge("A", "B", 1)
    graph.AddEdge("A", "C", 4)
    graph.AddEdge("B", "C", -2)
    graph.AddEdge("B", "D", 2)
    graph.AddEdge("C", "E", 3)
    graph.AddEdge("D", "E", 5)

    // 添加孤立的顶点，确保图中所有顶点都存在
    graph.AddVertex("E")

    // 执行 Bellman-Ford 算法
    distances, hasNegativeCycle := graph.BellmanFord("A")

    if hasNegativeCycle {
        fmt.Println("图中存在负权环")
    } else {
        fmt.Println("从顶点 A 到各个顶点的最短距离：")
        for vertex, distance := range distances {
            if distance == math.MaxInt32 {
                fmt.Printf("%s: ∞\n", vertex)
            } else {
                fmt.Printf("%s: %d\n", vertex, distance)
            }
        }
    }
}

执行结果输出如下所示：

从顶点 A 到各个顶点的最短距离：
D: 3
E: 2
A: 0
B: 1
C: -1

使用Go语言实现起来还是比较复杂，但是我们其实不用太关注，我们主要学习的是它的概念、思想。至于具体的实现，其实我们不一定说要能够完完整整的写出来。

results matching ""

    No results matching ""